Generalised Sequence Signatures through symbolic clustering.

Mining for Core Patterns in Stock Market Data.

Establishing relationships among patterns in stock market data.
The work under this grant has established several concepts for working with diverse data. As a first step, abstractions have been developed that appropriately represent the richness of data types such as sequence and graph data, and their combination with conventional data types such as Boolean (or item) data. As a second step towards integrating diverse data, techniques have been developed for establishing significance of attribute groups that correspond to a particular data source, and for finding significant relationships between attribute groups and Boolean attributes. Extraction of patterns from graph-relational data We have addressed the need for abstractions of graph data that go beyond characterizing the structure of the graph and rather also integrate information that is associated with graph nodes [2, 3, 1, 15]. We have developed techniques for determining which of those combined attributes are unexpected with respect to basic properties that are known from node data alone or based on simple graph correlations. Fig. 1 illustrates the concept of
Clustering sequences by overlap.

Pattern%2Dbased time%2Dseries subsequence clustering using radial distribution functions.

Subspace sums for extracting non%2Drandom data from massive noise.

Data mining of vector%2Ditem patterns using neighborhood histograms.

A pattern mining approach toward discovering generalized sequence signatures.
A pattern mining approach toward discovering generalized sequence signatures Typically, sequence signatures, such as motifs and domains, are assumed to be localized in one region of a sequence or are derived as combinations of the former. We generalize the concept of sequence signatures and introduce an algorithm for efficiently determining signatures based on subsequences that may be located anywhere on a sequence. In a preprocessing step, sequences are transformed into a feature space that is subsequently used to mine generalized signatures. We evaluate our signatures in relation to those in the Inter-Pro database and highlight the differences between them. A second comparison with InterPro shows that our signatures can be used to derive sequence annotations with a higher confidence. 1
Relating gene expression data on two%2Dcomponent systems to functional annotations in Escherichia coli.

Generalized Sequence Signatures through Symbolic Clustering.

An efficient weighted nearest neighbour classifier using vertical data representation.

Exploiting edge semantics in citation graphs using efficient%2C vertical ARM.

BISON bio%2Dinterface for the semi%2Dglobal analysis of network patterns.
BISON: bio-interface for the semi-global analysis of network patterns


Integration of profile hidden Markov model output into association rule mining.

Differential Association Rule Mining for the Study of Protein%2DProtein Interaction Networks.
Protein-protein interactions are of great interest to biologists. A variety of high-throughput techniques have been devised, each of which leads to a separate definition of an interaction network. The concept of differential association rule mining is introduced to study the annotations of proteins in the context of one or more interaction networks. Differences among items across edges of a network are explicitly targeted. As a second step we identify differences between networks that are separately defined on the same set of nodes. The technique of differential association rule mining is applied to the comparison of protein annotations within an interaction network and between different interaction networks. In both cases we were able to find rules that explain known properties of protein interaction networks as well as rules that show promise for advanced study.
Decision Tree Induction for Dynamic%2C High%2DDimensional Data Using P%2DTrees.
Decision Tree Induction is a powerful classification tool that is much used in practice and works well for static data with dozens of attributes. We adapt the decision tree concept to a setting where data changes rapidly and hundreds or thousands of attributes may be relevant. Decision tree branches are evaluated as needed, based on the most recent data, focusing entirely on the data that needs to be classified. Our algorithm is based on the P-tree data structure that allows fast evaluation of counts of data points, and results in scaling that is better than linear in the data set size.
A Kernel%2DBased Semi%2DNa%EFve Bayesian Classifier Using P%2DTrees.

PINE %2D Podium Incremental Neighbor Evaluator for Classifying Spatial Data.
Given a set of training data, nearest neighbor classification predicts the class value for an unknown tuple X by searching the training set for the k nearest neighbors to X and then classifying X according to the most frequent class among the k neighbors. Each of the k nearest neighbors casts an equal vote for the class of X. In this paper, we propose a new algorithm, Podium Incremental Neighbor Evaluator (PINE), in which nearest neighbors are weighted for voting. A metric called HOBBit is used as the distance metric, and a data structure, the P-tree    ,is  used for efficient implementation of the PINE algorithm on spatial data. Our experiments show that by using a Gaussian podium function, PINE outperforms the k-nearest neighbor (KNN) method in terms of classification accuracy for spatial data. In addition, in the PINE algorithm, all the instances are potential neighbors so that the value of k need not be prespecified as in KNN methods. By assigning high weights to the nearest neighbors and low (even zero) weights to other neighbors, high classification accuracy can be achieved.
Efficient Hierarchical Clustering of Large Data Sets Using P%2Dtrees.
Hierarchical clustering methods have attracted much attention by giving the user a maximum amount of flexibility. Rather than requiring parameter choices to be predetermined, the result represents all possible levels of granularity. In this paper a hierarchical method is introduced that is fundamentally related to partitioning methods, such as k-medoids and k-means, as well as to a density based method, namely center-defined DENCLUE. It is superior to both k-means and k-medoids in its reduction of outlier influence. Nevertheless it avoids both the time complexity of some partition-based algorithms and the storage requirements of density-based ones. An implementation is presented that is particularly suited to spatial-, stream-, and multimedia data, using P-trees    for efficient data storage and access.
Lazy Classifiers Using P%2Dtrees.
Lazy classifiers store all of the training samples and do not build a classifier until a new sample needs to be classified. It differs from eager classifiers, such as decision tree induction, which build a general model (such as a decision tree) before receiving new samples. K-nearest neighbor (KNN) classification is a typical lazy classifier. Given a set of training data, a knearest neighbor classifier predicts the class value for an unknown tuple X by searching the training set for the k nearest neighbors to X and then assigning to X the most common class among its k nearest neighbors. Lazy classifiers are faster at training time than eager classifiers, but slower at predicating time since all computation is delayed to that time. In this paper, we introduce approaches to efficient construction of lazy classifiers, using a data structure, Peano Count Tree (P-tree) .P-treeisa lossless and compressed representation of the original data that records the count information to facilitate efficient data mining. With P-tree structure, we introduced two classifiers, P-tree based k-nearest neighbor classifier (PKNN), and Podium Incremental Neighbor Evaluator (PINE). Performance analysis shows that our algorithms outperform classical KNN methods.
P%2Dtree Classification of Yeast Gene Deletion Data.
Genomics data has many properties that make it different from &#034;typical&#034; relational data. The presence of multi-valued attributes as well as the large number of null values led us to a P-tree-based bit-vector representation in which matching 1-values were counted to evaluate similarity between genes. Quantitative information such as the number of interactions was also included in the classifier. Interaction information allowed us to extend the known properties of one protein with information on its interacting neighbors. Different feature attributes were weighted independently. Relevance of different attributes was systematically evaluated through optimization of weights using a genetic algorithm. The AROC value for the classified list was used as the fitness function for the genetic algorithm.
